#include "generator-algorithm.h"
#include <gtest/gtest.h>
#include <fstream>
#include <iostream>
#include <list>
#include <boost/graph/adjacency_list.hpp>
#include <sstream>
#include "algo-support-reconnect.h"
#include <boost/foreach.hpp>
#include "algo-support-girth.h"
#include <algorithm>
#include <boost/graph/random.hpp>
#include "macros.h"
#include "algo-support-girth.h"
#include <functional>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <boost/property_map/property_map.hpp>
#include <numeric>
#include "algo-support-recorder.h"
#include "synchronizability-calc.h"
#include <vector>
#include "tools.h"
#include "FastDelegate.h"

#define foreach BOOST_FOREACH
#define foreach_reverse BOOST_REVERSE_FOREACH

/////////////////////////////
//                         //
// Define global functions //
//                         //
/////////////////////////////

namespace cccn
{

using namespace internal;
using namespace boost;
using namespace std;

Graph 
CreateCompleteGraph (uint n)
  {
  Graph g;
  for (uint u=0; u<n; u++)
    {
    for (uint v=u+1; v<n; v++)
      {
      g.Connect (u, v);
      }
    }
  return g;
  }


list<Graph> 
GrowGraph_k3 (const Graph& rootg, uint minGirth)
  {
  GraphMeasure rootgm (rootg);
  const uint n = rootgm.NumberOfNodes ();

  list<Graph> graphList;
  // try all possible ways to connect the two-edge-three-node structure into the root graph
  for (uint v1=0; v1<n; v1++) // v1 is the one end of the incoming structure 
    {
    for (uint v2=v1;;) // v2 is the other ned of the incoming structure
      {
      v2++;
      if (v2 >= n)
        {
        break;
        }
      // start trying
      const uint new_v1 = n;
      const uint new_v2 = n+1;
      Graph newg = rootg;      
      newg.Connect (v1, new_v1);
      newg.Connect (new_v1, new_v2);
      newg.Connect (new_v2, v2);

      // skip including the resultant grown graph newg, if the new nodes so connected
      // create a circuit shorter than 'minGirth'
      if (minGirth <= 3 || minGirth <= NodeMinCircuitFinder (new_v1, newg).GetLength ())
        {        
        graphList.insert (graphList.end (), newg);
        }
      }
    }

  return graphList;  
  }

list<Graph> 
ReconnectGraph_odd_k (const Graph& given_g)
  {
  // a counter to step through all possible reconnection patterns
  ReconnectionPatternCounter_odd_k counter (given_g);
  list<Graph> all_g;

  do
    {
    all_g.push_back (given_g);
    Graph& g = all_g.back ();
    do
      {
      // obtain an edge that needs to be reconnected
      vector<uint> reconnectEdge = counter.GetEdgeToReconnect ();
      const uint root = reconnectEdge[0];
      const uint to_old = reconnectEdge[1];
      const uint to_new = reconnectEdge[2];
      // do reconnect
      g.Disconnect (root, to_old);
      g.Connect (root, to_new);

      } while (counter.NextEdgeToReconnect ());
    } while (counter.NextReconnectionPattern ());

  return all_g;
  }

bool 
MappedValueIsLessThan (const map<uint, uint>::value_type& v1, const map<uint, uint>::value_type& v2)
  {
  return v1.second < v2.second;
  }

uint 
CalculateMinCircuitLength (Graph& g)
  {
  vector<uint> all_girth = CalculateAllMinCircuitLength (g);

  vector<uint>::const_iterator min_girth_it =
  min_element (all_girth.begin (), all_girth.end ());
  return *min_girth_it;
  }

vector<uint> 
CalculateAllMinCircuitLength (Graph& g)
  {
  typedef boost::graph_traits<BoostGraph_t>::vertex_iterator Vertex_it_t;
  typedef boost::graph_traits<BoostGraph_t>::vertex_descriptor Vertex_t;

  BoostGraph_t& boost_g = g.GetBoostGraph ();
  // size of the graph
  const uint n = GraphMeasure (g).NumberOfNodes ();
  // each entry is (node id, circuit length), where the 'circuit length' is the
  // length of the minimum circuit passing through the 'node id'
  typedef vector<uint> CircuitLengthMap_t;
  CircuitLengthMap_t circuitLengthMap (n, 0);

  // go through all nodes in the graph and calculate their associated girth
  Vertex_it_t begin, end;
  tie (begin, end) = vertices (boost_g);
  for (Vertex_it_t v_it=begin; v_it!=end; v_it++)
    { 
    // find the girth associated to the vertex v
    const Vertex_t v = *v_it;
    const uint v_id = get (vertex_index, boost_g, v);    
    NodeMinCircuitFinder finder (v_id, g);
    // update the result
    const uint length = finder.GetLength ();
    circuitLengthMap[v_id] = length;
    put (boost::vertex_girth, boost_g, v, length);
    }

  return circuitLengthMap;
  }

template <typename Container>
class BfsDistanceRecordVistor : public default_bfs_visitor
  {
  private:
    typedef boost::property_map<BoostGraph_t, boost::vertex_index_t>::type VertexIdMap_t;
    typedef boost::iterator_property_map<typename Container::iterator, VertexIdMap_t> DistanceMap_t;
    typedef boost::distance_recorder<DistanceMap_t, boost::on_tree_edge> DistanceRecorder_t;
  public:
    BfsDistanceRecordVistor (Container& distance, Graph& g) 
      : m_recorder (DistanceMap_t (distance.begin (), get (vertex_index, g.GetBoostGraph ())))
      {}

    template <typename E, typename G>
    void tree_edge (E e, G g)
      {
      m_recorder (e, g);
      }

  private:
    DistanceRecorder_t m_recorder;
  };

template <typename Container> 
BfsDistanceRecordVistor<typename Container>
MakeBfsDistanceRecordVistor (typename Container& distance, Graph& g)
  {
  return BfsDistanceRecordVistor<typename Container> (distance, g);
  }

vector<uint> 
CalculateAllDistanceSum_Bfs (Graph& g)
  {
  typedef boost::graph_traits<BoostGraph_t>::vertex_iterator v_it_t;

  BoostGraph_t& boost_g = g.GetBoostGraph ();
  const uint g_size = GraphMeasure (g).NumberOfNodes ();
  vector<uint> allDistSum (g_size, 0);

  v_it_t begin_it, end_it;
  tie (begin_it, end_it) = vertices (boost_g);
  for (v_it_t v_it = begin_it; v_it != end_it; v_it++)
    {
    vector<int> nodeDistSum (g_size, 0);
    // calculate distance from the vertex *v_it to all other vertices
    boost::breadth_first_search(boost_g, *v_it, 
      boost::visitor (MakeBfsDistanceRecordVistor (nodeDistSum, g)));
    // calculate the sum
    const uint v_id = get (vertex_index, boost_g, *v_it);
    uint sum = 0;
    foreach (uint d, nodeDistSum)
      {
      sum += d;
      }
    allDistSum[v_id] = sum;
    }

  return allDistSum;
  }

vector<uint> 
CalculateAllDistanceSum_Johnson (Graph& g)
  {
  // prepare a 2D matrix for storing all shortest path distance results
  const uint g_size  = GraphMeasure (g).NumberOfNodes ();
  const uint g_edges = GraphMeasure (g).NumberOfEdges ();
  BoostGraph_t& boost_g = g.GetBoostGraph ();
  vector<vector<uint> > all_dist = vector<vector<uint> > (g_size, vector<uint> (g_size, 0));

  // prepare an all-ones vector for supplying edge weight
  vector<uint> all_ones = vector<uint> (g_edges, 1);
  typedef property_map<BoostGraph_t, edge_index_t>::type EdgeIdPmap_t;
  typedef vector<uint>::iterator Iterator_t;
  iterator_property_map<Iterator_t, EdgeIdPmap_t> all_ones_pmap (all_ones.begin (), get (edge_index, boost_g));

  // start calculating all shortest path distance
  johnson_all_pairs_shortest_paths (
    boost_g, 
    all_dist,
    weight_map (all_ones_pmap)
    );

  // calculate the distance-sum of all nodes
  vector<uint> all_node_sumdist = vector<uint> (g_size, 0);
  for (uint s=0; s<all_dist.size (); s++)
    {
    const vector<uint>& nodedist = all_dist[s];
    for (uint d=s+1; d<nodedist.size (); d++)
      {      
      const uint dist = nodedist[d];
      all_node_sumdist[s] += dist;
      }
    }

  // return the results
  return all_node_sumdist;
  }

vector<uint> 
CalculateAllDistanceSum (Graph& g)
  {
  return CalculateAllDistanceSum_Johnson (g);
  }

double 
CalculateDistanceAverage (Graph& g)
  {
  vector<uint> all_node_sumdist = CalculateAllDistanceSum (g);
  const uint g_size = GraphMeasure (g).NumberOfNodes ();

  double sumdist = 0;
  foreach (uint node_sumdist, all_node_sumdist)
    {
    sumdist += node_sumdist;
    }

  return sumdist * 2.0 / (g_size * (g_size-1));
  }

/**
 * Test if a graph has the correct girth as expected
 *
 * \param size number of nodes of a graph
 * \param girth the girth of a graph
 * \return true if the graph's girth is correct; false otherwise
 */
bool 
IsCorrectGirth (uint size, uint girth)
  {
  // each (g, n) specify the correct grith,g, for a graph whose size is n or larger
  static const uint correctGirth[] = {
  // g = 3,4, 5, 6, 7, 8, 9,10  
         4,6,10,14,24,30,58,70};
  static const int correctGirthLen = sizeof (correctGirth) / sizeof (int);

  int location = upper_bound (correctGirth, correctGirth+correctGirthLen, size) - correctGirth - 1;
  uint expected_girth = location + 3;
  bool isCorrectGirth = girth >= expected_girth;

  return isCorrectGirth;
  }

/**
 * \return true if the girth of a graph equals to expected value
 */
bool
IsCorrectGraphGirth (const Graph& g)
  {
  return IsCorrectGirth (GetSize (g), GetGirth (g));
  }

/**
 * Rank graphs in the backtracking queues so that they are searched in a BFS style
 * eigenvalue included
 */
bool 
CandidateGraphIsLess (const Graph& g1, const Graph& g2)
  {
  const uint g1_size = GraphMeasure (g1).NumberOfNodes ();
  const uint g2_size = GraphMeasure (g2).NumberOfNodes ();
  const uint g1_sumGirth = g1.GetBoostGraph ()[graph_bundle].sumGirth;
  const uint g2_sumGirth = g2.GetBoostGraph ()[graph_bundle].sumGirth;
  const uint g1_girth = g1.GetBoostGraph ()[graph_bundle].girth;
  const uint g2_girth = g2.GetBoostGraph ()[graph_bundle].girth;
  const double g1_avgd = g1.GetBoostGraph ()[graph_bundle].avgDistance;
  const double g2_avgd = g2.GetBoostGraph ()[graph_bundle].avgDistance;
  const double g1_sync = g1.GetBoostGraph ()[graph_bundle].syncValue;
  const double g2_sync = g2.GetBoostGraph ()[graph_bundle].syncValue;

  if (g1_size != g2_size)
    {
    return g1_size > g2_size;
    }
  else if (g1_girth != g2_girth)
    {
    return g1_girth > g2_girth;
    }
  else if (g1_sumGirth != g2_sumGirth)
    {
    return g1_sumGirth > g2_sumGirth;
    }
  else if (abs (g1_avgd - g2_avgd) > 0.001)
    {
    return g1_avgd < g2_avgd;
    }
  else 
    {
    if (abs (g1_sync - g2_sync) > 0.001)
      {
      return g1_sync > g2_sync;
      }
    else
      {
      return false;
      }
    }
  }

bool
CandidateGraphIsEqual (const Graph& g1, const Graph& g2)
  {
  return !CandidateGraphIsLess (g1,g2) && !CandidateGraphIsLess (g2,g1);
  }

/// \return go to the position of a list specified by the parameter 'index'
list<Graph>::iterator 
GotoList (list<Graph>& C, uint index)
  {
  list<Graph>::iterator it = C.begin ();
  for (uint i=0; i<index; i++)
    {
    it++;
    }
  return it;
  }

/**
 * Merge the reconnected graphs into the queue for subsequence iteration - origin algorithm
 */
template <typename G> void 
GraphListMerger_origin (list<G>& root_g, list<G>& all_max_girth_g, const G& previous_g)
  {
  // sort all candidates in the correct ranking
  root_g.splice (root_g.end (), all_max_girth_g);
  root_g.sort (CandidateGraphIsLess);
  // select one among all best candiates uniformly at random
  list<G>::iterator upper = upper_bound (root_g.begin (), root_g.end (), root_g.front (), CandidateGraphIsLess);
  root_g.erase (upper, root_g.end ());
  const uint rand_int = RandomInt (root_g.size ()-1);
  DEBUG_LOG (root_g.size () << " best candidates, choose " << rand_int);
  root_g.push_front (*GotoList (root_g, rand_int));
  root_g.resize (1);
  }

/**
 * within the entire backtracking queue, insert all candidate graphs of the next size into the 
 * position n places hehind the front, or the end of all graphs of the current size, whichever goes
 * nearer to the front.
 *
 * \param to the backtracking queue
 * \param from the list container of all new candidate graphs of the next size
 * \param n the maximum places the insertion point can be behind the front
 *
 * \return an iterator pointing to the insertion position
 */
template <typename G> typename list<G>::iterator
InsertTo (list<G>& to, list<G>& from, uint n)
  {
  list<G>::iterator it_insert = to.begin ();

  while (true)
    {
    if (n == 0)
      {      
      break;
      }
    if (to.empty ())
      {
      break;
      }
    if (it_insert == to.end ())
      {
      break;
      }    
    if (GetSize (*it_insert) == GetSize (from.front ()))
      {
      break;
      }
    if (GetSize (*it_insert) != GetSize (to.front ()))
      {
      break;
      }

    it_insert++;
    n--;
    }

  list<G>::iterator it_insert_begin;
  if (it_insert == to.begin ())
    {    
    to.splice (it_insert, from);
    it_insert_begin = to.begin ();
    }
  else
    {
    it_insert_begin = it_insert;
    it_insert_begin--;
    to.splice (it_insert, from);
    it_insert_begin++;
    }
  
  return it_insert_begin;
  }

bool 
GraphSizeIsLess (const Graph& g1, const Graph& g2)
  {
  return GetSize (g1) < GetSize (g2);
  }

bool
GraphSizeNotEqual (const Graph& g1, const Graph& g2)
  {
  return GetSize (g1) != GetSize (g2);
  }

class GraphSizeIsNot
  {
  public:
    GraphSizeIsNot (uint size) : m_size (size) {}
    bool operator () (const Graph& g) {return GetSize (g) != m_size;}
  private:
    uint m_size;
  };

class GraphSizeIsLessThan
  {
  public:
    GraphSizeIsLessThan (uint size) : m_size (size) {}
    bool operator () (const Graph& g) {return GetSize (g) < m_size;}
  private:
    uint m_size;
  };

class GraphSizeIsGreaterThan
  {
  public:
    GraphSizeIsGreaterThan (uint size) : m_size (size) {}
    bool operator () (const Graph& g) {return GetSize (g) > m_size;}
  private:
    uint m_size;
  };

/**
 * Count the number of graphs for each size in the backtracking queue
 */
template <typename G> void
CountBacktrackQueue (const list<G>& queue)
  {
  vector<uint> all_g_size;
  vector<uint> all_g_size_no;

  foreach (const G& g, queue)
    {
    const uint g_size = GetSize (g);

    if (all_g_size.empty ())
      {
      all_g_size.push_back (g_size);
      all_g_size_no.push_back (1);
      }
    else 
      {
      if (all_g_size.back () != g_size)
        {
        all_g_size.push_back (g_size);
        all_g_size_no.push_back (1);
        }
      else
        {
        all_g_size_no.back ()++;
        }
      }    
    }

  cout << "size =  ";
  ShowVector (std::cout, all_g_size, 4);
  cout << "count = ";
  ShowVector (std::cout, all_g_size_no, 4);
  }

/**
 * count the number of graphs of the next size
 */
template <typename G> uint
CountNextGraph (const list<G>& queue)
  {
  list<G>::const_iterator it = queue.begin ();
  const uint size = GetSize (*it);

  uint count = 0;
  while (it != queue.end () && size == GetSize (*it))
    {
    count++;
    it++;
    }

  return count;
  }

/**
 * Extract all future candidate graphs into another container, where
 * a future graph is defined whose graph size is larger than the next size
 *
 * \param future the container to be inserted with all future candidate graphs
 * \param current the current backtracking queue
 * \param next_size the next size to be processed by the algorithm
 */
template <typename G> void
SpliceFutureGraphsTo (list<G>& future, list<G>& current, uint next_size)
  {
  list<G>::iterator it_begin = find_if (current.begin (), current.end (), GraphSizeIsGreaterThan (next_size));
  list<G>::iterator it_end = it_begin;

  if (it_begin != current.end ())
    {
    it_end = find_if (it_begin, current.end (), GraphSizeIsLessThan (GetSize (*it_begin)));
    future.splice (future.begin (), current, it_begin, it_end);
    }
  }

/**
 * \return the maximum size in the backtracking queue
 */
template <typename G> uint 
GetMaxGraphSize (const list<G>& queue)
  {
  list<G>::const_iterator it = queue.begin ();
  uint max_size = 0;

  while (it != queue.end ())
    {
    uint cur_size = GetSize (*it);
    max_size = max (max_size, cur_size);

    it++;
    if (it == queue.end () || cur_size > GetSize (*it))
      {
      break;
      }
    }
  return max_size;
  }

/**
 * Merge the reconnected graphs into the queue for subsequence iteration - improved algorithm
 */
template <typename G> void 
GraphListMerger_improved (list<G>& root_g, list<G>& all_max_girth_g, const G& previous_g)
  {
  // at least this number of graphs of the current size are processed before going into the next size
  static const uint BatchSize = 30;
  const uint prev_size = GetSize (previous_g);

  if (!all_max_girth_g.empty ())
    {  
    const uint next_size = GetSize (all_max_girth_g.front ());
    // extract all future graphs into the 'future_g'
    list<G> future_g;
    SpliceFutureGraphsTo (future_g, root_g, next_size);

    // insert the new cadidate graphs into the backtracking queue at the appropriate position,
    //   and find the range of all next sized candidate graphs
    list<G>::iterator it_rootg_begin_sortg = InsertTo (root_g, all_max_girth_g, BatchSize-1);
    list<G>::iterator it_rootg_end_sortg = find_if (it_rootg_begin_sortg, root_g.end (), GraphSizeIsNot (GetSize (*it_rootg_begin_sortg)));

    // sort all the next sized candidate graphs and remove 'maybe' homogenous counterparts
    list<G> sort_g;
    sort_g.splice (sort_g.begin (), root_g, it_rootg_begin_sortg, it_rootg_end_sortg);
    sort_g.sort (CandidateGraphIsLess);
    sort_g.unique (CandidateGraphIsEqual);    
    // put back the future graphs into the backtracking queue
    if (!future_g.empty ())
      {
      InsertTo (sort_g, future_g, BatchSize-1);
      }
    root_g.splice (it_rootg_end_sortg, sort_g);
    }

  // check if it is about to go into the next sized graphs ...
  const uint cur_size = GetSize (root_g.front ());    
  if (cur_size == GetMaxGraphSize (root_g) && prev_size != cur_size)
    {
    // .. if yes, check if there exists a graph among the next sized graphs
    //    whose girth equals the expected value
    if (IsCorrectGraphGirth (root_g.front ()))
      {
      // ... if yes, proceed to the next sized graph (do nothing here)
      }
    else
      {
      // ... otherwise, backtracking.
      list<G> future_g;      
      SpliceFutureGraphsTo (future_g, root_g, cur_size-1);
      InsertTo (root_g, future_g, BatchSize);
      }
    }
  else
    {
    // ... if the next size does not yet arrive, continue processing the graphs of the current size
    //   (do nothing here)
    }

  // debugging: stream to std::cout the status of the backtracking queue 'root_g' 
  CountBacktrackQueue (root_g);
  }

/**
 * while merging new candidate graphs into the backtracking queue, this class
 * remember the number of graphs that have already been iterated. This number
 * is than used to bound from above the number of iterations spent on each size
 */
class GraphListMergerWithUpperBound
  {
  public:
    GraphListMergerWithUpperBound () : m_count (1), m_cur_size (0) 
      {}
    void operator () (list<Graph>& root_g, list<Graph>& all_max_girth_g, const Graph& previous_g)
      {
      static const uint m_MaxNextGraphCount = 1000;

      // perform the original merging among the new candidate graphs and the backtracking queue
      GraphListMerger_improved (root_g, all_max_girth_g, previous_g);

      // count the number of iterations spent on the current size
      const uint g_size = GetSize (root_g.front ());
      if (g_size > m_cur_size)
        {
        m_count = 1;
        m_cur_size = g_size;
        }
      else if (g_size == m_cur_size)
        {
        m_count++;
        }

      // purge the backtracking queue if there are too many iterations on the current size 
      if (m_count >= m_MaxNextGraphCount)
        {
        list<Graph> future_g;
        SpliceFutureGraphsTo (future_g, root_g, m_cur_size);
        root_g.clear ();
        root_g.splice (root_g.end (), future_g);
        }
      }

  private:
    uint m_count;
    uint m_cur_size;
    
  };

/**
 * The original alogrithm to generate a tidy graph, which iterates step by step by
 * retaining only the maximum girth, maximum sum girth, smallest average distance graphs at each step
 */
template <typename DebugVisitor, typename MergeFunctor>
Graph 
GenerateTidyGraphTemplate_k3 (const uint n, MergeFunctor merge, typename DebugVisitor& vis)
  {
  // a new graph in the next iteration step is generated growing a graph in 'root_g'
  list<Graph> root_g;
  // the first graph in root_g is the 'seed_g'
  Graph seed_g = CreateCompleteGraph (4);
  seed_g.GetBoostGraph ()[graph_bundle].girth = 3;
  seed_g.GetBoostGraph ()[graph_bundle].sumGirth = 12;
  seed_g.GetBoostGraph ()[graph_bundle].avgDistance = 1;
  root_g.push_back (seed_g);

  Graph g;
  while (true)
    {
    g = root_g.front ();    
    root_g.pop_front ();

    // visitor action
    vis.RootGraph (g);

    if (GraphMeasure (g).NumberOfNodes () >= n)
      {
      // visitor action
      vis.IterationEnd (root_g);

      break;
      }

    if (true) //GraphMeasure (g).NumberOfNodes () < n)
      {    
      // set the maximum of min-girth to be the girth of the current graph.
      // this is necessary when backtracking occurs, and the maxGirth
      // needs to be reduced
      const uint currentGirth = g.GetBoostGraph ()[graph_bundle].girth;
      // grow the graph
      list<Graph> all_grown_g = GrowGraph_k3 (g, currentGirth-1);

      // contain all the greatest min-girth graph
      list<Graph> all_max_girth_g;    
      uint maxGirth = 0;
      foreach (Graph& grown_g, all_grown_g)
        {
        // visitor action
        vis.GrownGraph (grown_g);

        // do reconnection
        list<Graph> all_reconnected_g = ReconnectGraph_odd_k (grown_g);
        
        // check girth, sum-girth, and avg-distance of each reconnected graph
        foreach (Graph& reconnect_g, all_reconnected_g)
          {       
          // calculate graph characteristics
          double avg_dist = CalculateDistanceAverage (reconnect_g);
          vector<uint> all_node_girth = CalculateAllMinCircuitLength (reconnect_g);
          uint min_girth = *min_element (all_node_girth.begin (), all_node_girth.end ());
          uint sum_girth = accumulate (all_node_girth.begin (), all_node_girth.end (), 0);
          SynchronizabilityCalc sync (reconnect_g);
          double syncvalue = sync.GetSyncValue ();
          double syncratio = sync.GetSyncRatio ();


          // skip the reconnected graphs whose girth are smaller than the root graph
          const uint size = GetSize (reconnect_g);
          if (min_girth < currentGirth || !IsCorrectGirth (size, min_girth+1))
            {
            continue;
            }

          // update internal graph properties
          ostringstream gname;
          gname << "G" << GetSize (reconnect_g);
          reconnect_g.GetBoostGraph ()[graph_bundle].name = gname.str ();
          reconnect_g.GetBoostGraph ()[graph_bundle].girth = min_girth;
          reconnect_g.GetBoostGraph ()[graph_bundle].sumGirth = sum_girth;
          reconnect_g.GetBoostGraph ()[graph_bundle].avgDistance = avg_dist;
          reconnect_g.GetBoostGraph ()[graph_bundle].syncValue = syncvalue;
          reconnect_g.GetBoostGraph ()[graph_bundle].syncRatio = syncratio;

          // visitor action
          vis.ReconnectedGraph (reconnect_g);

          if (min_girth > maxGirth)
            {
            maxGirth = min_girth;
            }
          all_max_girth_g.push_back (reconnect_g);
          }
        } 
      merge (root_g, all_max_girth_g, g);
      }

    // visitor action
    vis.IterationEnd (root_g);
    }

  return g;
  }

template <typename DebugVisitor>
Graph 
GenerateTidyGraphTemplate_origin_k3 (const uint n, typename DebugVisitor& vis)
  {
  fastdelegate::FastDelegate3<list<Graph>&, list<Graph>&, const Graph&> merger (&GraphListMerger_origin);
  return GenerateTidyGraphTemplate_k3 (n, merger, vis);
  }

template <typename DebugVisitor>
Graph 
GenerateTidyGraphTemplate_improved_k3 (const uint n, typename DebugVisitor& vis)
  {
  return GenerateTidyGraphTemplate_k3 (n, GraphListMergerWithUpperBound (), vis);
  }

Graph 
GenerateTidyGraph_k3 (uint n)
  {
  return GenerateTidyGraphTemplate_origin_k3 (n, GenerateTidyGraphEmptyDebugVisitor ());
  }

}; // namespace cccn

/////////////
//         //
// Testing //
//         //
/////////////

using namespace cccn;

TEST (GraphOrderingTest, CorrectGirth)
  {
  // each (g, n) specify the correct grith,g, for a graph whose size is n or larger
  const uint correctGirth[] = {
  // g = 3,4, 5, 6, 7, 8, 9,10  
         4,6,10,14,24,30,58,70};
  const int correctGirthLen = sizeof (correctGirth) / sizeof (int);

  EXPECT_EQ (8, correctGirthLen);

  for (uint size=4; size<100; size++)
    {
    for (uint girth=3; girth<9; girth++)
      {
      bool isCorrectGirth = IsCorrectGirth (size, girth);
      if (size < correctGirth[girth-3 + 1])
        {
        EXPECT_TRUE (isCorrectGirth) << "(size,girth) = (" << size << "," << girth << ")";
        }
      else
        {
        EXPECT_FALSE (isCorrectGirth) << "(size,girth) = (" << size << "," << girth << ")";
        }
      }
    }
  }

class CreateCompleteGraphTest : public ::testing::TestWithParam<uint>
  {};

TEST_P (CreateCompleteGraphTest, NumberOfEdgeTest)
  {
  uint n = GetParam ();
  
  Graph g = CreateCompleteGraph (n);
  GraphMeasure m (g);

  EXPECT_EQ (n, m.NumberOfNodes ());
  EXPECT_EQ (n*(n-1)/2, m.NumberOfEdges ()) << "Incorrect number of edges when n = " << n;

  DEBUG_PRINT_GRAPH ("complete-graph-" << n, g);
  }

INSTANTIATE_TEST_CASE_P (CreateCompleteGraph, CreateCompleteGraphTest, ::testing::Range<uint> (2,10));

class GrowGraph_k3Test : public ::testing::TestWithParam<uint>
  {};

TEST_P (GrowGraph_k3Test, NumberOfNodesAndEdgesOfResultantGraphsTest)
  {
  uint n = GetParam ();

  Graph g = CreateCompleteGraph (n);

  list<Graph> listGraph = GrowGraph_k3 (g);
  EXPECT_EQ (n*(n-1)/2, listGraph.size ());

  uint i=1;
  for (list<Graph>::iterator it=listGraph.begin ();
    it != listGraph.end ();
    it ++, i++)
    {
    Graph& printg = *it;
    GraphMeasure printgm (printg);

    EXPECT_EQ (n*(n-1)/2+3, printgm.NumberOfEdges ()) << "Incorrect number of edges with n = " << n << " and version = " << i;
    EXPECT_EQ (n+2, printgm.NumberOfNodes ()) << "Incorrect number of nodes with n = " << n << " and version = " << i;

    DEBUG_PRINT_GRAPH ("Out/complete-graph-" << n << "-grown-version-" << i, printg);
    }
  }

TEST_P (GrowGraph_k3Test, MinGirthParameterTest)
  {
  Graph g;
  // number of nodes
  const uint n = GetParam ();
  // create a ring network with n nodes
  for (uint i=0; i<n; i++)
    {
    g.Connect (i, (i+1) % n);
    }

  for (uint minGirth=0;; minGirth++)
    {
    list<Graph> all_grown_g = GrowGraph_k3 (g, minGirth);

    uint skip = 0;
    if (minGirth > 4)
      {
      skip = (minGirth-4) * n;
      }
    if (skip > n*(n-1)/2 || minGirth >= n)
      {
      break;
      }
    EXPECT_EQ (n*(n-1)/2 - skip, all_grown_g.size ()) 
      << "minGirth = " << minGirth
      << ", n = " << n;
    }

  }

INSTANTIATE_TEST_CASE_P (SmallNetTest, GrowGraph_k3Test, ::testing::Values<uint> (10,20,2));

TEST (ReconnectGraph_odd_kTest, k3Test)
  {
  typedef boost::graph_traits<BoostGraph_t>::vertex_iterator vertex_iterator;  

  const uint k = 3;
#ifdef _DEBUG
  const uint n = 6;
#else
  const uint n = 30;
#endif

  list<Graph> all_g;
  all_g.push_back (CreateCompleteGraph (k+1));

  uint g_index = 1;
  uint root_index = 0;
  while (true)
    {
    Graph g = all_g.front ();
    all_g.pop_front ();

    const uint g_size = GraphMeasure (g).NumberOfNodes ();

    // print each root graph
    DEBUG_PRINT_GRAPH ("k3-n" << setfill ('0') << setw (3) << g_size 
      << "-root" << setfill ('0')  << setw (4) << root_index, g);

    if (g_size > n)
      {
      break;
      }

    list<Graph> all_grown_g = GrowGraph_k3 (g);
    list<Graph> all_reconnected_g;

    uint growth_index = 0;
    foreach (Graph& grown_g, all_grown_g)
      {
      // print each grown graph
      DEBUG_PRINT_GRAPH ("k3-n" << setfill ('0')  << setw (3) << g_size 
        << "-root" << setfill ('0')  << setw (4) << root_index 
        << "-growth" << setfill ('0')  << setw (2) << growth_index, grown_g);

      list<Graph> some_reconnected_g = ReconnectGraph_odd_k (grown_g);      

      // check if all node degree are k
      uint reconnect_index = 0;
      foreach (Graph& reconnected_g, some_reconnected_g)
        {
        // print each reconnected graph
        DEBUG_PRINT_GRAPH ("k3-n" << setfill ('0')  << setw (3) << g_size 
          << "-root" << setfill ('0')  << setw (4) << root_index 
          << "-growth" << setfill ('0')  << setw (2) << growth_index 
          << "-reconnect" << setfill ('0')  << setw (2) << reconnect_index
          << "-g" << setfill ('0')  << setw (4) << g_index++, reconnected_g);

        const BoostGraph_t& reconnected_boost_g = reconnected_g.GetBoostGraph ();
        vertex_iterator begin, end;
        boost::tie (begin, end) = vertices (reconnected_boost_g);

        for (vertex_iterator it=begin; it!=end; it++)
          {
          const uint v_id = get (vertex_index, reconnected_boost_g, *it);
          EXPECT_EQ (k, out_degree (*it, reconnected_boost_g)) << "v_id = " << v_id << ", growth_index = " << growth_index << ", reconnect_index = " << reconnect_index;
          }
        reconnect_index++;
        }

      EXPECT_TRUE (some_reconnected_g.size () == 18 || some_reconnected_g.size () == 8) 
        << "current graph size = " << g_size 
        << ", some_reconnected_g.size () = " << some_reconnected_g.size ()
        << ", growth_index = " << growth_index;

      all_reconnected_g.splice (all_reconnected_g.end (), some_reconnected_g);
      growth_index++;
      }

    EXPECT_EQ (g_size * (g_size-1) / 2, all_grown_g.size ()) << "current graph size = " << g_size;
    EXPECT_GE (g_size * (g_size-1) / 2 * 18, all_reconnected_g.size ()) << "current graph size = " << g_size;
    EXPECT_LE (g_size * (g_size-1) / 2 * 8, all_reconnected_g.size ()) << "current graph size = " << g_size;

    vector<Graph> selector (all_reconnected_g.begin (), all_reconnected_g.end ());
    all_g.push_back (selector[rand () % selector.size ()]);
    //all_g.splice (all_g.end (), all_reconnected_g);
    root_index++;
    }
  }

class CalculateMinCircuitLengthTest : public ::testing::TestWithParam <uint>
  {};

TEST_P (CalculateMinCircuitLengthTest, RingNetTest)
  {
  Graph g;
  const uint n = GetParam ();
  for (uint i=0; i<n; i++)
    {
    g.Connect (i, (i+1)%n);
    }
  EXPECT_EQ (n, CalculateMinCircuitLength (g));
  }

INSTANTIATE_TEST_CASE_P (GenRing, CalculateMinCircuitLengthTest, ::testing::Range<uint> (10, 21, 2));

bool BigGirthSmallSizeFirst (const Graph& g1, const Graph& g2)
  {
  const uint g1_size = GraphMeasure (g1).NumberOfNodes ();
  const uint g2_size = GraphMeasure (g2).NumberOfNodes ();
  const uint g1_girth = g1.GetBoostGraph ()[graph_bundle].girth;
  const uint g2_girth = g2.GetBoostGraph ()[graph_bundle].girth;

  if (g1_girth != g2_girth)
    {
    return g1_girth > g2_girth;
    }
  else
    {
    return g1_size < g2_size;
    }
  }

class GirthLessThan : public unary_function <const Graph&, bool>
  {
  public:
    GirthLessThan (const uint girth) : m_girth_bound (girth)
      {}

    result_type operator () (argument_type g)
      {
      return g.GetBoostGraph ()[graph_bundle].girth < m_girth_bound;
      }

  private:
    const uint m_girth_bound;
  };

/**
 * Print the root graph in each iteration
 */
class PrintK3GraphDebugVisitor : public GenerateTidyGraphEmptyDebugVisitor
  {
  public:
    PrintK3GraphDebugVisitor (string prefix = "") : m_root_index (0), m_prefix (prefix)
      {}

    template <typename G> void RootGraph (G& g)
      {
      const BoostGraph_t& boost_g = g.GetBoostGraph ();

      const uint n = GraphMeasure (g).NumberOfNodes ();
      const uint girth = boost_g[graph_bundle].girth;
      const uint sum_girth = boost_g[graph_bundle].sumGirth;
      const double avg_dist = boost_g[graph_bundle].avgDistance;

      PRINT_GRAPH (m_prefix <<
        "root" << setfill ('0') << setw (4) << m_root_index <<
        "-k3-n" << setfill ('0') << setw (3) << n <<
        "-sumgirth" << sum_girth <<
        "-girth" << girth <<
        "-avgdist" << setprecision (2) << fixed << avg_dist, g);

      m_root_index++;
      }

    template <typename Container> void IterationEnd (Container& queue_g) 
      {
      cout << "finished " << m_root_index << "-iteration. queue size = " << queue_g.size () << "." << endl;
      }
  private:
    uint m_root_index;
    const string m_prefix;
  };

TEST (MinGirthGraphTest, GenerateTidyGraph_origin_k3Test)
  {
  const uint n = 40;
  GenerateTidyGraphProgressRecorder vis ("origin-db.dat");
  Graph g = GenerateTidyGraphTemplate_origin_k3 (n, vis);

  PRINT_GRAPH ("origin-k3-n" << n, g);
  }

TEST (MinGirthGraphTest, GenerateTidyGraph_improved_k3Test)
  {
  const uint n = 100;
  GenerateTidyGraphProgressRecorder vis ("improved-db.dat");
  Graph g = GenerateTidyGraphTemplate_improved_k3 (n, vis);

  PRINT_GRAPH ("improved-k3-n" << n, g);
  }


TEST (MinGirthGraphTest, DISABLED_GenerateTidyGraph_origin_k3Test)
  {
  const uint n = 20;
  Graph g = GenerateTidyGraphTemplate_origin_k3 (n, PrintK3GraphDebugVisitor ("origin-"));

  PRINT_GRAPH ("origin-k3-n" << n, g);
  }

class SumGirthLessThan : public unary_function <const Graph&, bool>
  {
  public:
    SumGirthLessThan (const uint sumGirth) : m_sumGirth_bound (sumGirth)
      {}

    result_type operator () (argument_type g)
      {
      return g.GetBoostGraph ()[graph_bundle].sumGirth < m_sumGirth_bound;
      }

  private:
    const uint m_sumGirth_bound;
  };

class CalculateDistanceSumTest : public ::testing::TestWithParam <uint>
  {
  protected:
    // setup a Ring network
    virtual void SetUp() 
      {
      const uint n = GetParam ();

      for (uint i=0; i<n; i++)
        {
        m_g.Connect (i, (i+1)%n);
        }
      }

    Graph m_g;
  };

TEST_P (CalculateDistanceSumTest, DISABLED_NodeDistanceBfsAlgoTest)
  {
  const uint n = GetParam ();
  vector<uint> all_distance = CalculateAllDistanceSum_Bfs (m_g);

  foreach (uint d, all_distance)
    {
    EXPECT_EQ (d, (n-1)*(n+1)/4);
    }
  }

TEST_P (CalculateDistanceSumTest, NodeDistanceTest)
  {
  const uint n = GetParam ();
  vector<uint> all_distance = CalculateAllDistanceSum (m_g);

  foreach (uint d, all_distance)
    {
    EXPECT_EQ (d, (n-1)*(n+1)/4);
    }
  }

TEST_P (CalculateDistanceSumTest, AverageDistanceTest)
  {
  const uint n = GetParam ();
  double avg_dist = CalculateDistanceAverage (m_g);

  EXPECT_EQ (avg_dist, 1.0 * (n-1)*(n+1) / (4*n));
  }

INSTANTIATE_TEST_CASE_P (ManyRingNet, CalculateDistanceSumTest, ::testing::Range<uint> (11,51,2));

//    BFS algorithm test results
//
//    Note: Google Test filter = *CalculateAllDistanceSumTest*
//    [==========] Running 20 tests from 1 test case.
//    [----------] Global test environment set-up.
//    [----------] 20 tests from ManyRingNet/CalculateAllDistanceSumTest
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/0
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/0 (78 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/1
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/1 (109 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/2
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/2 (156 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/3
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/3 (234 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/4
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/4 (344 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/5
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/5 (469 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/6
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/6 (609 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/7
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/7 (781 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/8
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/8 (985 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/9
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/9 (1234 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/10
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/10 (1500 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/11
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/11 (1813 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/12
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/12 (2187 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/13
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/13 (2578 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/14
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/14 (3016 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/15
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/15 (3500 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/16
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/16 (4047 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/17
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/17 (4656 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/18
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/18 (5328 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/19
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/19 (6063 ms)
//    [----------] 20 tests from ManyRingNet/CalculateAllDistanceSumTest (39703 ms total)
//    
//    [----------] Global test environment tear-down
//    [==========] 20 tests from 1 test case ran. (39703 ms total)
//    [  PASSED  ] 20 tests.
//    
//      YOU HAVE 4 DISABLED TESTS
//    
//    Press any key to continue . . .


//    Johnson algorithm test results
//
//    Note: Google Test filter = *CalculateAllDistanceSumTest*
//    [==========] Running 20 tests from 1 test case.
//    [----------] Global test environment set-up.
//    [----------] 20 tests from ManyRingNet/CalculateAllDistanceSumTest
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/0
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/0 (16 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/1
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/1 (0 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/2
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/2 (16 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/3
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/3 (15 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/4
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/4 (16 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/5
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/5 (15 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/6
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/6 (16 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/7
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/7 (16 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/8
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/8 (31 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/9
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/9 (16 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/10
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/10 (31 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/11
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/11 (47 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/12
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/12 (31 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/13
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/13 (47 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/14
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/14 (31 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/15
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/15 (47 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/16
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/16 (46 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/17
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/17 (63 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/18
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/18 (62 ms)
//    [ RUN      ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/19
//    [       OK ] ManyRingNet/CalculateAllDistanceSumTest.RingNetTest/19 (79 ms)
//    [----------] 20 tests from ManyRingNet/CalculateAllDistanceSumTest (657 ms total)
//    
//    [----------] Global test environment tear-down
//    [==========] 20 tests from 1 test case ran. (657 ms total)
//    [  PASSED  ] 20 tests.
//    
//      YOU HAVE 4 DISABLED TESTS
//    
//    Press any key to continue . . .
